package 链表.圆圈中最后剩下的数字;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/3/23 15:21
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(lastRemaining(10, 17));
    }


    //TODO 待优化 当m为1时的测试案例无法通过
    public static int lastRemaining(int n, int m) {
        Node root = makeCyclicList(n);
        Node p = root.next;
        while (p.next != p){
            //TODO 这里需要注意!!
            for (int i = 1; i < m-1; i++) {
                p = p.next;
            }
            Node q = p.next;
            p.next = q.next;
            p = p.next;
        }
        return p.val;
    }

//构建循环链表
    public static Node makeCyclicList(int n){
        Node root = new Node(-1);
        Node head = new Node(0);
        root.next = head;
        head.next = head;
        Node p = head;
        for (int i = 1; i < n ; i++) {
            Node node = new Node(i);
            p.next = node;
            p = p.next;
            if (i == n - 1){
                p.next = head;
            }
        }
        return root;
    }
}
